#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
#define lchid(x): (2*x)
#define rchild(x): (2*x+1)
vector<int> arr;
//[0,1,2,3,4,5,6,7,8,9,10]
/**
 *                     1
 *              2           3
 *          4       5    6      7
 *      8      9
 */
void fixHeap(vector<int> &arr, int k, int len)
{
    arr[0] = arr[k];
    for (int i = 2 * k; i <= len; i *= 2)
    {
        if (i < len && arr[i] < arr[i + 1])
            i++;
        if (arr[0] >= arr[i])
            break;
        else
        {
            arr[k] = arr[i];
            k = i;
        }
    }
    arr[k] = arr[0];
}
void BuildHeap(vector<int> &arr)
{
    int n = arr.size();
    for (int i = (n + 1) / 2; i >= 1; --i)
    {
        fixHeap(arr, i, n);
    }
}
void HeapSort(vector<int> &arr)
{
    int len = arr.size() - 1;
    while (len > 0)
    {
        swap(arr[1], arr[len]);
        fixHeap(arr, 1, --len);
    }
}
int main()
{
    arr = {0, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2, 10, 10, 1, 1, 2, 7, 8, 9, 9};
    BuildHeap(arr);
    for (int i = 1; i < arr.size(); ++i)
        printf(" %d", arr[i]);
    HeapSort(arr);
    printf("\n");
    for (int i = 1; i < arr.size(); ++i)
        printf(" %d", arr[i]);
    printf("\n");
    return 0;
};